package NC20_数字字符串转化成IP地址;

/*
import java.util.*;


public class Solution {
*/
/*
*
     * @param s string字符串
     * @return string字符串ArrayList

*//*


    boolean justify(String s){
        if (s.length() == 1 && s.charAt(0) == '0' || Integer.parseInt(s) > 255){
            return false;
        }
        return true;
    }
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> list = new ArrayList<>();

        for (int i = 1; i <= 3; i++){   // 第一位的长度，合法值在[0-255]，所以最多长度为3
            for (int j = 1; j <= 3; j++){
                for (int m = 1; m <= 3; m++){
                    for (int n = 1; n <= 3; n++){
                        if ((i + j + m + n) == s.length()){
                            String s1 = s.substring(0, i);
                            String s2 = s.substring(i, i + j);
                            String s3 = s.substring(i + j, i + j + m);
                            String s4 = s.substring(i + j + m, i + j + m + n);
                            if (justify(s1) && justify(s2) && justify(s3) && justify(s4)){
                                String res = s1 + "." + s2 + "." + s3 + "." + s4;
                                list.add(res);
                            }
                        }
                    }
                }
            }

        }
        return list;
    }

}

*/

import java.util.ArrayList;

public class Solution {
    /**
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    ArrayList<String> result = new ArrayList<>();
    
    public ArrayList<String> restoreIpAddresses (String s) {
        restoreIpAddresses(s, 0, new ArrayList<String>());
        return result;
    }

    private void restoreIpAddresses(String s, int startIndex, ArrayList<String> paths) {
        // 当凑出有效的 IP 地址回溯，即 paths.size() == 4 回溯
        if (paths.size() == 4){
            result.add(paths.get(0) + "." + paths.get(1) + "." + paths.get(2) + "." + paths.get(3));
            return;
        }

        // 每个 IP 地址段的长度可能为 1 ~ 3, 所以我们需要搜索这三种可能性
        for (int i = startIndex; i < startIndex + 3 && i < s.length(); i++){
            // 截取当前 IP 地址
            String subStr = (paths.size() == 3) ? s.substring(startIndex, s.length()) :
                    s.substring(startIndex, i + 1);

            // 解析当前 IP 地址值
            Integer subNum = Integer.parseInt(subStr);
            // 如果 IP 地址合法
            if (subNum >= 0 && subNum <= 255){
                // 将当前合法的 IP 地址段添加到 paths 中
                paths.add(subNum.toString());

                // 递归搜索
                restoreIpAddresses(s, i + 1, paths);
                // 恢复现场
                paths.remove(paths.size() - 1);
            }else {
                // 当前的 IP 地址不符合要求时开始回溯
                return;
            }

            if (paths.size() == 3){
                break;
            }
        }
    }


}